// 1042113.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include "stdio.h"

#include "vector"
//---------------------------------
//--Thu vien doc file
#include "fstream"
#include "iostream"
using namespace std;
//---------------------------------

#define MAX 100
//---------------------------------
class Canh
{
public:
	int u;
	int U() const { return u; }
	void U(int val) { u = val; }
	int v;
	int V() const { return v; }
	void V(int val) { v = val; }
protected:

private:
};
class PrimAlg
{
public:
	//--Ham doc file
	void GetData(const char *filename);
	//--Ham xuat ra man hinh
	void OutScreen();
	//--Ham Prim
	void Run(int v0, int dinh);
	//--Ham chon dinh
	void ChonDinhV(int v);
	//--Ham tim canh
	int TimCanh(Canh &e, int &trongso);
	//--Ham chon canh
	void ChonCanh(Canh e);
	//--Ham sap xep canh
	void SapXepCanh1(Canh &e);
	void SapXepCanh2(int canh);

	int FindConnected();
	void Visit(int i, int label);
	int Dem(int i);
	void Run2();

	void LuuTru();
	void SapXep();
	int TestGraph();
	void WriteData(const char *filename);
protected:
	//---------------------------------
	//--Thanh phan Ma tran ke
	//---So dinh cua Ma tran ke
	int nVertex;
	//---Ma tran ke
	int M[MAX][MAX];
	//---------------------------------
	//--Mang X
	int X[MAX];
	int nX;
	//--Mang Y
	int Y[MAX];
	int nY;
	//--Mang Canh
	Canh C[MAX];
	int nC;
	//--Mang Canh da sap xep
	Canh D[MAX];
	int nD;
	//--Trong so
	int trongso;
	//--Nhan cua cac dinh
	int labels[MAX];
	//--
	Canh E[MAX][MAX];
	int nE;
	int F[MAX];
	int nF;
	Canh G[MAX][MAX];
	int nG1;
	int nG2;
private:
};
//---------------------------------
//--Gan nhan tat ca TPLT
int PrimAlg::FindConnected()
{
	int label;
	for(int i = 0; i < nVertex; i++)
	{
		labels[i] = 0;
	}
	label = 0;
	for (int i = 0; i < nVertex; i++)
	{
		if (labels[i] == 0)
		{
			label ++;
			Visit(i,label);
		}
	}
	return label;
}
int PrimAlg::Dem(int i)
{
	int kq = 0;
	for (int j = 0; j < nVertex; j++)
	{
		if (labels[j] == i)
		{
			kq ++;
		}
	}
	return kq;
}
//--Gan nhan 1 TPLT
void PrimAlg::Visit(int i, int label)
{
	labels[i] = label;
	for (int j = 0; j<nVertex; j++)
	{
		if ((labels[j] == 0) && (M[i][j] || M[j][i]))
		{
			Visit(j,label);
		}
	}
}
void PrimAlg::Run(int v0, int dinh)
{
	//--X la tap cac dinh cua do thi
	for (int i = 0; i < nVertex; i++)
	{
		X[i] = i;
	}
	nX = nVertex;
	int nT = 0;
	trongso = 0;
	nY = 0;
	nC = 0;
	//--Buoc 1: Chon dinh v0 va khoi tao Y={v0}
	ChonDinhV(v0);
	//--Buoc 2: Trong so nhung canh e noi dinh w voi dinh v0 ta chon canh co trong luong nho nhat
	while(nT < dinh - 1)
	{
		//--Buoc 3: Y= Y + {w} va T = T + {e}
		//--Buoc 4: Neu T = n - 1 phan tu thi dung, nguoc lai sang buoc 2
		Canh e;
		if (TimCanh(e, trongso) == 1)
		{
			nT = nT + 1;
		}
	}
	SapXepCanh2(nT);
}
//--Ham hoan vi
void Hoanvi(int &a,int &b)
{
	int c;
	c = a;
	a = b;
	b = c;
}
//--Ham sap xep canh
void PrimAlg::SapXepCanh1(Canh &e)
{
	if (e.u > e.v)
	{
		Hoanvi(e.u,e.v);
	}

}
//--Ham Chon canh
void PrimAlg::ChonCanh(Canh e)
{
	int min = -1;
	SapXepCanh1(e);
	C[nC] = e;
	nC = nC + 1;
}
//---------------------------------
void PrimAlg::ChonDinhV(int v)
{

	//--Y=Y+{v}
	Y[nY]=v;
	nY++;
	//--X=X\{v}
	//--Tim vi tri muon xoa
	int vitri;
	for(int i = 0; i <nX; i++)
	{
		if(X[i] == v)
		{
			vitri = i;
			break;
		}
	}
	for(int i = vitri; i < nX; i++)
	{
		X[i] = X[i+1];
	}
	nX = nX - 1;
}
//--Ham tim canh
int PrimAlg::TimCanh(Canh &e, int &trongso)
{
	int dinh;
	int x1;
	int y1;
	int min = -1;
	for (int i = 0; i < nX; i ++)
	{
		for (int j = 0; j < nY; j++)
		{
			y1 = Y[j];
			x1 = X[i];
			if (( min == -1 && M[x1][y1] > 0 )|| (( M[x1][y1] > 0 ) && ( M[x1][y1] < min )))
			{
				min = M[x1][y1];
				e.u = x1;
				e.v = y1;
				dinh = x1;
			}
		}
	}
	if(min == -1)
	{
		return 0;
	}
	else
	{
		trongso += min;
		ChonDinhV(dinh);
		ChonCanh(e);
		return 1;
	}
}
//--Ham doc file
void PrimAlg::GetData(const char *filename)
{
	//--Nhap du lieu tu tap tin van ban
	ifstream fin;
	fin.open(filename);
	fin >> nVertex;
	for (int i=0;i<nVertex;++i)
	{	
		for (int j=0;j<nVertex;++j)
		{
			fin >> M[i][j];
		}
	}
	fin.close();
}
void PrimAlg::SapXepCanh2(int canh)
{
	nD = 0;
	for (int i = 0; i < nVertex; i++)
	{
		for (int j = 0;j < canh; j++)
		{
			if(C[j].u == i)
			{
				D[nD] = C[j];
				nD = nD + 1;
			}
		}
	}
	for (int i = 0; i < nD; i++)
	{
		for (int j = 0;j < nD; j++)
		{
			if ((D[i].u == i) &&(D[j].u == i) && (D[i].v > D[j].v)) 
			{
				Hoanvi(D[i].u,D[j].u);
				Hoanvi(D[i].v,D[j].v);
			}
		}
	}
}
//---------------------------------
//--Ham xuat ra man hinh
void PrimAlg::OutScreen()
{
	int a = 0;
	int b1 = 0;
	while (G[a][b1].u > -1)
	{
		int b = 0;
		while (G[a][b].u > -1)
		{
			if(b == 0)
			{
				printf("%d\n",G[a][b].u);	
			}
			else if(G[a][b+1].u > -1)
			{
				printf("(%d,%d);",G[a][b].u,G[a][b].v);
			}
			else
			{
				printf("(%d,%d)",G[a][b].u,G[a][b].v);
			}
			b = b + 1;
		}
		printf("\n");
		a = a + 1;
	}
}

void PrimAlg::LuuTru()
{	
	int j = 1;
	E[nE][0].u = trongso;
	for (int i = 0; i < nD; i++)
	{
		E[nE][j++] = D[i];
	}
	nE ++;
}
//--Ham Run2
void PrimAlg::SapXep()
{
	for (int i = 0; i < nE; i++)
	{

	}
	nG1 = 0;
	for (int i = 0; i < nVertex - 1; i++)
	{
		for (int j = 0; j < nF; j++)
		{
			if (F[j] == i)
			{
				int k = 0;
				nG2 = 0;
				while(E[j][k].u > -1)
				{
					G[nG1][nG2] = E[j][k];
					k++;
					nG2++;
				}
				nG1 ++;
			}
		}

	}
}
int PrimAlg::TestGraph()
{
	//--Kiem tra do thi co huong hay khong
	for (int i=0;i<nVertex;i++)
	{
		for (int j=0 ; j< nVertex;j++)
		{
			if (M[i][j]!= M[j][i])
			{
				return 0;
			}
		}
	}
	//--Kiem tra ma tran co hop le hay khong
	for (int i=0;i<nVertex;i++)
	{
		if (M[i][i]!=0)
		{
			return 0;
		}
	}
	return 1;
}
void PrimAlg::Run2()
{
	nF = 0;
	nE = 0;
	int i = FindConnected();
	int c;
	for (int k = 1; k <= i; k++)
	{
		int b = Dem(k);
		for (int j = 0; j <= nVertex; j++)
		{
			if(labels[j] == k)
			{
				c = j;
				break;
			}
		}
		Run(c,b);
		LuuTru();
	}
	SapXep();
	OutScreen();
}
void PrimAlg::WriteData(const char *filename)
{
	//--Ghi file
	ofstream fin;
	fin.open(filename);



	//--------------------------
	int a = 0;
	int b1 = 0;
	while (G[a][b1].u > -1)
	{
		int b = 0;
		while (G[a][b].u > -1)
		{
			if(b == 0)
			{
				fin << (G[a][b].u) << "\n";	
			}
			else if(G[a][b+1].u > -1)
			{
				fin << "(" << G[a][b].u << "," << (G[a][b].v) << ");";
			}
			else
			{
				fin << "(" << G[a][b].u << "," << (G[a][b].v) << ")";
			}
			b = b + 1;
		}
		fin << "\n";
		a = a + 1;
	}


	//--------------------------
	fin.close();
}
void main(int argc, char * argv[])
{
	if(argc == 3)
	{
		PrimAlg P;
		P.GetData(argv[1]);
		int kq = P.TestGraph();
		if(kq == 1)
		{
			P.Run2();
			P.WriteData(argv[2]);
		}
		else
		{
			printf("Ma tran nhap sai \n");
		}
	}
	else
		printf("Tham so dong lenh nhap sai\n");

}

